package com.chenken.recursion;

/**
 *	上楼梯-递归
 *  楼梯有n阶台阶,每次往上走1步,或每次往上走2步 
 *	假设n阶台阶有f(n)种走法,第1步有2种走法
 *		如果第1步上1阶,那就还剩n-1阶, 共f(n-1)种走法
 *		如果第1步上2阶,那就还剩n-2阶,共f(n-2)种走法
 *	所以f(n) = f(n-1) + f(n-2)
 *
 *	状态转移方程	f(n) = f(n-1) + f(n-2)
 *	
 */
public class ClimbStairs {

	/**
	 * 	暴力递归
	 * @param n
	 * @return
	 */
	public static int climbStairs01(int n) {
		if(n <= 2) return n;
		return climbStairs01(n-1) + climbStairs01(n-2);
	}
	
	/**
	 *  记忆化搜索
	 * @param n
	 * @return
	 */
	public static int climbStairs02(int n) {
		if(n <= 2) return n;
		int[] dp = new int[n+1];
		dp[1] = 1;
		dp[2] = 2;
		return climbStairs(n,dp);
	}
	
	private static int climbStairs(int n, int[] dp) {
		if(dp[n] == 0) {
			dp[n] = climbStairs(n-1,dp) + climbStairs(n-2,dp);
		}
		return dp[n];
	}
	
	/**
	 * 	非递归
	 * @param n
	 * @return
	 */
	public static int climbStairs03(int n) {
		if(n <= 2) return n;
		int first = 1;
		int second = 2;
		for(int i = 3;i<=n;i++) {
			second = first + second;
			first = second - first;
		}
		return second;
	}

	public static void main(String[] args) {
		int num = 5;
		System.out.println(climbStairs01(num));
		System.out.println(climbStairs02(num));
		System.out.println(climbStairs03(num));
	}
}
